The present invention relates to methods and apparatus for producing a halftone (screened) reproduction of a latent or real image from a digital representation of a black and white or color image by an output device used in the printing and pre-printing industry.
Halftone is the reproduction of continuous tone art work, such as a photograph, through a series of dots of various sizes and locations used to simulate grays or color tones.
In general, digital halftoning is accomplished by either binary (1 bitxe2x80x94two levels) or multi-bit (multi-level) halftoning methods. In binary digital halftoning, a continuous tone image is converted into a halftone image consisting of a pattern of dots. Each dot within the halftone image is either xe2x80x9cONxe2x80x9d (black) or xe2x80x9cOFFxe2x80x9d (white). More specifically, binary digital halftoning converts a plurality of digitized intensity values representing a continuous tone image into a plurality of halftone cells, each halftone cell corresponding to an intensity value. The number of dots within each halftone cell is proportional to the magnitude of each corresponding intensity value.
During binary digital halftoning, each intensity value is spatially mapped into a corresponding halftone cell, having a plurality of black and white dots.
In operation, a binary digital halftoning system compares each intensity value to a matrix of threshold levels and generates a halftone cell corresponding to each intensity value. Typically, the threshold matrix has a number of elements equivalent to the number of dots in the halftone cell. To generate the binary halftone cell, a given intensity value is compared to each threshold level in the matrix. Each dot in the halftone cell, that corresponds to a threshold level in the threshold level matrix that is lesser in value than the intensity value, is made black; otherwise, the dot is white. Thus, the intensity value is mapped into an area comprised of an arrangement of black and white dots whose overall intensity is corresponding to the magnitude of the intensity value.
Multi-level halftoning is an extension of binary halftoning. In multi-level halftoning, each dot in the halftone cell has a multi-bit value. Many display devices, some digital printing devices and other marking devices permit multi-level pixel reproduction; multi-level halftoning takes advantage of this capability.
Typically, these devices are limited as to the number of levels that they can produce. In contrast, sampling devices can produce many different output levels. Multi-level halftoning is used to convert a large number of tone levels into a lesser number of levels. For instance, if a display device can accurately display sixteen levels while a scanner can provide a 256 level intensity value, a multi-level halftoning system must distribute each single 256 level value into a halftone cell containing a plurality of sixteen level dots, so that, when viewed, will appear as the 256 level value.
Reference is now made to FIG. 1, which is a schematic block diagram of a prior art halftoning technique, as described in U.S. Pat. Nos. 4,350,996 and 4,456,924 assigned to Scitex Corp. Ltd. This halftoning technique is very well known and many vendors such as AGFA, Linotype-Hell, Dainippon Screen etc. have used different versions of it. Screen threshold values are pre-calculated and stored in a screen threshold value matrix 30xe2x80x94a memory that can be described as a two-dimensional array or matrix. The screen threshold values may be stored permanently, or calculated specifically according to some required parameters defined for a specific job. In either case, the screen threshold values should be stored in the screen threshold value matrix 30 prior to the beginning of the screening (halftoning) process.
During the screening process, screen threshold values are compared, by means of a comparator 60, with image data, temporarily stored in the image value buffer 40. During halftoning, the image data is read from the image value buffer 40 and may be modified, e.g. for calibration purposes, by calibration look-up table 50. In some prior-art embodiments, the calibration LUT 50 may exist in another section of the system, or may not exist at all, and the calibration function is performed by other means.
The output 65 of the comparison performed by the comparator 60 is a binary halftone output, namely, one-bit data that serves as the control for the printing engine. In this case, the printer is capable of either printing a full mark (dot) on the substrate (the halftone output bit is xe2x80x9c1xe2x80x9d or xe2x80x9cONxe2x80x9d) or not printing at this point at all (the halftone output bit is xe2x80x9c0xe2x80x9d or xe2x80x9cOFFxe2x80x9d).
The reading of screen threshold values from the screen threshold value matrix 30 may be sequential, value by value and line by line. In such a case, the address calculator 20 performs as a simple count-up counter. There may, however, be more complex address calculations performed by address calculator 20, including skipping of cells in the screen threshold value matrix, or even more complex address calculations such as angled scanning of the matrix. In case of an angled scanning of the matrix 30 cells, the resulting output halftone image will be a screened (halftone) reproduction that composes an angled screen.
Typically, image values and screen threshold values are each represented by an eight bit digital number. The halftone output, however, is a one-bit number. The number of bits that compose the X address-coordinate 25 and Y address-coordinate 35 may vary, depending on the size of the matrix 30. A typical small matrix 30 of 16 by 16 entries may be addressed by a four-bit number for the X address-coordinate 25 and another four-bit number for the Y address-coordinate 35. A large but still typical matrix 30 may be composed of a 1024 by 1024 two-dimensional array, addressed by ten bit numbers for each of the X and Y address-coordinates. Such a large matrix 30 is capable of representing a very accurate and sophisticated halftone cell or a combination of a number of halftone cells in a super cell arrangement. For a super cell arrangement, even a large matrix 30 of 4096 by 4096 entries may be considered. For such a matrix, a 12-bit number is required for each of the X and Y address-coordinates.
FIG. 2 is a simplified example of the arrangement and data composition of the screen threshold value matrix 30 of FIG. 1. In this simplified example, the matrix 30 is composed of entries 70 in a two-dimensional five by five array. The content of the entries is designed to reproduce a typical square halftone dot. Different contents of the entries 70 will result in different shapes of the output halftone dot. It should be noted that the shapes of the various output halftone dots are a representation of the matrix 30 contents, and a larger image value results in a larger size of the output halftone pixel, since it comprises a larger number of xe2x80x9cONxe2x80x9d dots.
FIGS. 3A and 3B illustrate, by way of example, the output halftone pixels corresponding to intensity values of 10 and 20 respectively, using the threshold matrix of FIG. 2. In these examples, the matrix contents dictates square dots of a size proportional to the input intensity value.
FIG. 4 schematically illustrates another prior art screening method, as described in U.S. Pat. No. 5,444,551 assigned to Eastman Kodak Company. The method presented is a generalized method for providing a mechanism for performing multi-level half-toning of continuous tone images.
In this prior art system, various dot arrangements are defined and associated with all possible image values. These dot arrangements are stored in a plurality of two-dimensional arrays. A typical variety of 256 different image values requires 256 arrays for storing all possible dot arrangements. The entire halftoning system may be described as a three-dimensional array (memory) in which the X and Y axes correspond to the X and Y axes on the printed media, and the Z (height) axis corresponds to the image value at a location in the XY plane. In this embodiment, output may be a one bit, or multi bit, depending on the number of bits assigned for each location in the three-dimensional memory.
During the halftoning process, each (x, y) location on the printed media is transformed to its relative (xxe2x80x2, yxe2x80x2) location within the three-dimensional halftoning array. The calculated xxe2x80x2 and yxe2x80x2, together with the image intensity value, compose an address to a memory cell within the three-dimensional array. The data obtained from this cell is the output halftone data.
It should be noted that this embodiment enables completely different dot arrangements and sizes for different image intensity values, since a separate matrix is assigned to each intensity value. For example, for a specific image value the dot shape may be round, with dot coverage of 40%, for the next image value the dot may be a star, with coverage of 90% and the next image value may result in a dispersed xe2x80x9crandomxe2x80x9d arrangement with 50% coverage. This embodiment is, therefore, much more flexible than the embodiment of FIG. 1, where a single threshold matrix serves for all image values, determining a similar dot arrangement, as illustrated in FIGS. 2, 3A and 3B. The xe2x80x9cpenaltyxe2x80x9d in using the embodiment of FIG. 4 may be the need for a large memory. For example, a matrix 30 of FIG. 1, of 1000 by 1000 cells requires 1 Mbytes (one million memory cells). A corresponding memory size constructed for the embodiment of FIG. 4 requires 32 Mbytes for one bit halftone output, or 128 Mbytes for four-bit halftone output. In applications that use smaller arrays for storing the various dot arrangements, the overall memory size may be xe2x80x9creasonablexe2x80x9d. For example, 256 dot arrangements of 64 by 64 cells, with four-bit output halftone, require 0.5 Mbytes. It should also be noted that most industrial embodiments do not use this method, and that the embodiment of FIG. 1 is much more common.
According to the invention, a new approach is adopted regarding the definition of the halftoning values.
An aspect of the invention is a method for determining said values, which comprises the steps of:
providing pairs of image coordinates defining addresses in a digital image;
deriving from each said coordinate pair a screen reference value;
providing the digital intensity values of said digital image corresponding to said address-coordinates; and
deriving a halftone value from each image intensity value and the corresponding screen reference value.
The term xe2x80x9caddressxe2x80x9d is used in this specification and claims, unless otherwise stated, in a geometrical sense, viz. to indicate a point or location in an image or in a part thereof.
Screen reference values are digital values, each of which is derived from an address as defined above.
By xe2x80x9cscreen reference value correspondingxe2x80x9d to a image intensity value is meant the screen reference value defined for the image address to which said image value corresponds.
A first transformation module is preferably used to derive from each said coordinate pair a screen reference value, and a second transformation module is preferably used to derive a halftone value from each image intensity value and the corresponding screen reference value.
The first and second transformation modules may each be a two-dimensional matrix or a LUT or a calculator, operable to perform arithmetic operations.
In embodiments of the invention, the said digital image intensity values may be calibrated before feeding them to said second transformation module.
Another aspect of the invention is an apparatus for producing a halftone image, which comprises:
storage means for storing digital image intensity values, each corresponding to an image address, viz. to a pair of image coordinates;
first transformation means for receiving image coordinates and deriving therefrom a screen reference value for each said address; and
second transformation means for receiving said screen reference values from said first transformation means, receiving from said storage means corresponding digital image values, and deriving a halftone value from each reference value and the corresponding digital image value.
The first and second transformation means may each be a two-dimensional matrix, a LUT or a calculator, operable to perform arithmetic operations.
In embodiments of the invention, the apparatus may comprise calibration means for receiving the digital image values and providing modified values to be fed to the second transformation means.
The advantages of the invention can be illustrated by considering the case that both transformation means or modules are LUTs. In this case, rather than use, in effect, a 3D LUT, the present invention describes a re-distribution of the information in such a way as to use two 2D LUTs in series. This leads to a considerable saving of space and computational complexity over prior art methods and apparatus, achieved by discarding redundant screen values. In principle, two 2D LUTs cannot hold all the information that an equivalent 3D LUT holds, and their use may result in loss of some tone values. If, however, the discarded values are redundant ones, then there is no loss of any real information and there will be no degradation whatsoever of screening quality. Redundancy, in the context of the present invention, means that same threshold values exist for a plurality of image addresses, enabling the use of a representative code instead of the actual threshold values.
Also, in practical terms, there is no loss of flexibility and no added complexity. Two 2D LUTs are created, which completely separate the xe2x80x98geometricalxe2x80x99 (X,Y) addressing from the thresholding aspects. The intermediate parameter connecting the two new 2D LUTs is the screen reference value. According to this method, the inputs to the first 2D LUT are the (x, y) parameters and its output is a screen reference value which, in turn, together with an image intensity value, are the input entries to the second 2D LUT. The output from the second LUT is an N-bit halftone value, where N is an integer with a value greater than or equal to 1.
The redundancy in threshold combinations, namely, the fact that multiple (X,Y) combinations have the same screen reference value, enables this use of two 2D LUTs instead of one 3D LUT.